<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Nonnegative matrix factorization</title>
<link rel="canonical" href="/Users/mcgrant/Repos/CVX/examples/html/nonneg_matrix_fact.html">
<link rel="stylesheet" href="../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Nonnegative matrix factorization</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#plots">Plots</a>
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% Argyris Zymnis, Joelle Skaf, Stephen Boyd</span>
<span class="comment">%</span>
<span class="comment">% We are given a matrix A in R^{m*n}</span>
<span class="comment">% and are interested in solving the problem:</span>
<span class="comment">%</span>
<span class="comment">% minimize    ||A - Y*X||_F</span>
<span class="comment">% subject to  Y &gt;= 0, X &gt;= 0</span>
<span class="comment">%</span>
<span class="comment">% where Y in R{m*k} and X in R{k*n}.</span>
<span class="comment">% This script generates a random matrix A and obtains an</span>
<span class="comment">% *approximate* solution to the above problem by first generating</span>
<span class="comment">% a random initial guess for Y and the alternatively minimizing</span>
<span class="comment">% over X and Y for a fixed number of iterations.</span>

<span class="comment">% Generate data matrix A</span>
rstate = rand(<span class="string">'state'</span>);
m = 10; n = 10; k = 5;
A = rand(m,k)*rand(k,n);

<span class="comment">% Initialize Y randomly</span>
Y = rand(m,k);

<span class="comment">% Perform alternating minimization</span>
MAX_ITERS = 30;
residual = zeros(1,MAX_ITERS);
<span class="keyword">for</span> iter = 1:MAX_ITERS
    cvx_begin <span class="string">quiet</span>
        <span class="keyword">if</span> mod(iter,2) == 1
            variable <span class="string">X(k,n)</span>
            X &gt;= 0;
        <span class="keyword">else</span>
            variable <span class="string">Y(m,k)</span>
            Y &gt;= 0;
        <span class="keyword">end</span>
        minimize(norm(A - Y*X,<span class="string">'fro'</span>));
    cvx_end
    fprintf(1,<span class="string">'Iteration %d, residual norm %g\n'</span>,iter,cvx_optval);
    residual(iter) = cvx_optval;
<span class="keyword">end</span>

<span class="comment">% Plot residuals</span>
plot(residual);
xlabel(<span class="string">'Iteration Number'</span>);
ylabel(<span class="string">'Residual Norm'</span>);

<span class="comment">% Display results</span>
disp( <span class="string">'Original matrix:'</span> );
disp( A );
disp( <span class="string">'Left factor Y:'</span> );
disp( Y );
disp( <span class="string">'Right factor X:'</span> );
disp( X );
disp( <span class="string">'Residual A - Y * X:'</span> );
disp( A - Y * X );
fprintf( <span class="string">'Residual after %d iterations: %g\n'</span>, iter, cvx_optval );
</pre>
<a id="output"></a>
<pre class="codeoutput">
Iteration 1, residual norm 3.94785
Iteration 2, residual norm 0.769086
Iteration 3, residual norm 0.606551
Iteration 4, residual norm 0.512622
Iteration 5, residual norm 0.393939
Iteration 6, residual norm 0.315434
Iteration 7, residual norm 0.238842
Iteration 8, residual norm 0.186361
Iteration 9, residual norm 0.146201
Iteration 10, residual norm 0.119986
Iteration 11, residual norm 0.0998441
Iteration 12, residual norm 0.0843896
Iteration 13, residual norm 0.0718356
Iteration 14, residual norm 0.0613885
Iteration 15, residual norm 0.0526807
Iteration 16, residual norm 0.0452945
Iteration 17, residual norm 0.0391095
Iteration 18, residual norm 0.0338531
Iteration 19, residual norm 0.0294337
Iteration 20, residual norm 0.025664
Iteration 21, residual norm 0.0224614
Iteration 22, residual norm 0.0197134
Iteration 23, residual norm 0.017333
Iteration 24, residual norm 0.0152406
Iteration 25, residual norm 0.0134003
Iteration 26, residual norm 0.011777
Iteration 27, residual norm 0.0103465
Iteration 28, residual norm 0.00908502
Iteration 29, residual norm 0.00797451
Iteration 30, residual norm 0.00699685
Original matrix:
  Columns 1 through 7

    0.7866    1.7239    1.3452    1.5511    1.3530    1.1933    1.1612
    1.1583    1.4047    1.3236    1.2878    1.1097    1.2681    1.4426
    1.2201    1.3939    0.9230    1.0590    1.1370    1.1894    1.0099
    1.6507    2.3825    2.0352    2.1016    1.9563    1.8618    1.9193
    1.5864    1.8379    1.2313    1.3710    1.5395    1.5604    1.3822
    1.3007    2.0306    1.5088    1.6731    1.6468    1.6124    1.6143
    0.8572    1.6265    1.4736    1.5347    1.3371    1.1011    1.1438
    0.5591    1.0591    1.0106    1.0441    0.8555    0.7072    0.7349
    1.4222    2.2313    1.6812    1.9507    1.7405    1.6636    1.4519
    0.9937    1.4187    0.4619    0.8417    1.1113    1.2318    0.9158

  Columns 8 through 10

    1.7782    0.9493    1.5523
    1.7846    0.6617    2.1024
    1.4058    0.7613    1.3088
    2.7211    1.4302    2.6015
    1.9030    1.0934    1.7194
    2.1933    1.1256    2.0814
    1.8244    1.0729    1.5531
    1.2005    0.6775    1.0536
    2.2397    1.1687    2.0234
    1.1330    0.5926    0.9621

Left factor Y:
   1.0e+05 *

    0.0000    0.0000    0.0000    2.1168    0.0000
    0.0000    0.0000    0.0000    0.0000    0.0000
    0.0000    0.0000    0.0000    2.5476    0.0000
    0.0000    0.0000    0.0000    5.0586    0.0000
    0.0000    0.0000    0.0000    5.3585    0.0000
    0.0000    0.0000    0.0000    4.1992    0.0000
    0.0000    0.0000    0.0000    4.0904    0.0000
    0.0000    0.0000    0.0000    1.7905    0.0000
    0.0000    0.0000    0.0000    1.2085    0.0000
    0.0000    0.0000    0.0000    2.2985    0.0000

Right factor X:
  Columns 1 through 7

    0.3098    0.5913    0.9738    0.8028    0.4787    0.4076    0.6940
    0.9900    0.9192    0.3031    0.4908    0.7101    0.9991    0.8312
    0.2808    0.1141    0.5344    0.3549    0.1240    0.0000    0.0048
    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000    0.0000
    0.9092    2.0158    0.6572    1.3862    1.4823    1.4247    0.7690

  Columns 8 through 10

    0.9972    0.4037    1.1560
    0.8375    0.2622    1.0135
    0.3097    0.2645    0.2437
    0.0000    0.0000    0.0000
    1.3240    0.8026    0.7696

Residual A - Y * X:
  Columns 1 through 7

   -0.0004   -0.0006    0.0004   -0.0001   -0.0003    0.0013   -0.0002
    0.0000   -0.0002    0.0001   -0.0000   -0.0002    0.0003   -0.0002
    0.0005    0.0007   -0.0006    0.0001    0.0004   -0.0017    0.0002
    0.0001    0.0001   -0.0001    0.0000    0.0001   -0.0003    0.0001
    0.0003    0.0005   -0.0003    0.0001    0.0002   -0.0011    0.0003
   -0.0006   -0.0010    0.0008   -0.0001   -0.0005    0.0023   -0.0003
    0.0002    0.0002   -0.0001    0.0000    0.0001   -0.0005    0.0002
    0.0003    0.0004   -0.0003    0.0001    0.0002   -0.0011    0.0002
    0.0006    0.0010   -0.0008    0.0001    0.0006   -0.0024    0.0002
   -0.0010   -0.0005   -0.0008   -0.0008   -0.0003    0.0041   -0.0002

  Columns 8 through 10

   -0.0000    0.0002   -0.0002
   -0.0001   -0.0001    0.0003
    0.0000   -0.0002    0.0003
    0.0000   -0.0001   -0.0000
    0.0001   -0.0003    0.0001
    0.0000    0.0003   -0.0004
    0.0001   -0.0002   -0.0001
    0.0000   -0.0002    0.0001
   -0.0001   -0.0002    0.0005
   -0.0006    0.0000   -0.0011

Residual after 30 iterations: 0.00699685
</pre>
<a id="plots"></a>
<div id="plotoutput">
<img src="nonneg_matrix_fact__01.png" alt=""> 
</div>
</div>
</body>
</html>